package com.chj.jz.dp.class02;

public class Code09_MinimumPathSum {
	/**
	 * @param grid:
	 *            a list of lists of integers
	 * @return: An integer, minimizes the sum of all numbers along its path
	 */
	public static int minPathSum(int[][] grid) {
		// write your code here

		int m = grid.length;
		if (m == 0) {
			return 0;
		}

		int n = grid[0].length;
		if (n == 0) {
			return 0;
		}

		int[][] pi = new int[m][n];
		int[][] f = new int[m][n];
		int i, j;
		for (i = 0; i < m; i++) {
			for (j = 0; j < n; j++) {

				if (i == 0 && j == 0) {
					f[i][j] = grid[i][j];
					continue;
				}

				int t = Integer.MAX_VALUE;
				if (i > 0) {
					t = Math.min(t, f[i - 1][j]);
					if (t == f[i - 1][j]) {
						pi[i][j] = 0;
					}
				}

				if (j > 0) {
					t = Math.min(t, f[i][j - 1]);
					if (t == f[i][j - 1]) {
						pi[i][j] = 1;
					}
				}

				f[i][j] = t + grid[i][j];
			}
		}

		int[] path = new int[m + n - 1];
		int x = m - 1;
		int y = n - 1;
		for (int p = 0; p < m + n - 1; p++) {
			path[p] = grid[x][y];
			if (pi[x][y] == 0) {
				x--;
			} else {
				y--;
			}
		}

		for (int p = m + n - 2; p >= 0; p--) {
			System.out.print(path[p] + " ");
		}
		System.out.println();
		return f[m - 1][n - 1];
	}

	public static void main(String[] args) {
		{
			int[][] arr = new int[][] { { 1, 5, 7, 6, 8 }, { 4, 7, 4, 4, 9 }, { 10, 3, 2, 3, 2 } };
			System.out.println(minPathSum(arr));
		}
		{
			int[][] arr = new int[][] { { 1, 3, 1 }, { 1, 5, 1 }, { 4, 2, 1 } };
			System.out.println(minPathSum(arr));
		}
		{
			int[][] arr = new int[][] { { 1, 3, 2 } };
			System.out.println(minPathSum(arr));
		}
	}
}
